import sys
input = sys.stdin.readline
def f1(x, y):
if x < 0 or y < 0:
return 0
else:
return d[x][y]
def f2(x, y):
if x < 0 or y < 0:
return 0
else:
return d[min(x, n-1)][min(y, m-1)]
q = [0]*2502
i = 2
while i <= 2501:
if q[i] == 0:
for j in range(i+i, 2501, i):
if q[j] == 0:
q[j] = 1
i += 1
n, m = map(int, input().split())
g = [list(map(int, list(input()[:-1]))) for _ in range(n)]
d = [[0]*m for i in range(n)]
d[0][0] = g[0][0]
for i in range(n):
for j in range(m):
d[i][j] = f1(i-1, j) + f1(i, j-1) - f1(i-1, j-1) + g[i][j]
c = 100000000
for k in range(2, max(n, m)+1):
if q[k] == 0:
s = 0
x = k*k
for i in range(k-1, n+k-1, k):
for j in range(k-1, m+k-1, k):
c1 = f2(i, j) - f2(i-k, j) - f2(i, j-k) + f2(i-k, j-k)
s += min(c1, x-c1)
c = min(s, c)
print(c)/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int getFlips(vector<vector<char>> &v,int r,int c,int k)
{
vector<int> arr(2,0);
for(int p = r;p<r+k;p++)
{
for(int q = c;q<c+k;q++)
{
if(p>=v.size() || q>=v[0].size()) arr[0]++;
else arr[(int)(v[p][q]-'0')]++;
}
}
return min(arr[0],arr[1]);
}
int sol(vector<vector<char>> &v,int n,int m,int k){
int sm = 0;
for(int i = 0;i<n;i+=k){
for(int j = 0;j<m;j+=k){
sm+=getFlips(v,i,j,k);
}
}
return sm;
// O(nm)
// 2500 * 2500 = 6250000
}
int main()
{
int n,m;
cin>>n>>m;
vector<vector<char>> v(n,vector<char>(m,'0'));
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cin>>v[i][j];
}
}
int minV = INT_MAX;
for(int k = 2;k<=20;k++)
minV = min(minV,sol(v,n,m,k));
cout<<minV<<endl;
return 0;
}
1703E - Mirror Grid | 1042A - Benches |
1676B - Equal Candies | 1705B - Mark the Dust Sweeper |
1711A - Perfect Permutation | 1701B - Permutation |
1692A - Marathon | 1066A - Vova and Train |
169B - Replacing Digits | 171D - Broken checker |
380C - Sereja and Brackets | 1281B - Azamon Web Services |
1702A - Round Down the Price | 1681C - Double Sort |
12A - Super Agent | 1709A - Three Doors |
1680C - Binary String | 1684B - Z mod X = C |
1003A - Polycarp's Pockets | 1691B - Shoe Shuffling |
1706A - Another String Minimization Problem | 1695B - Circle Game |
1702B - Polycarp Writes a String from Memory | 1701A - Grass Field |
489C - Given Length and Sum of Digits | 886B - Vlad and Cafes |
915A - Garden | 356A - Knight Tournament |
1330A - Dreamoon and Ranking Collection | 1692B - All Distinct |